package alo.p4.work;
import org.junit.Test;

import java.util.*;
//直方图中的最大矩形
public class MaxRectangleArea {
    //测试
    @Test
    public void test(){
        //int[] A=new int[]{3,2,1,2,3,2,1};
        int[] A=new int[]{8, 7, 5, 9, 3, 8, 7, 6, 5, 4};
        Solution3 solution3=new Solution3();
        long time=System.nanoTime();
        int j=solution3.MaxRectangleArea(A, 10);
        System.out.println(j+"");
        long estimatedTime = System.nanoTime() - time;
        System.out.println(estimatedTime);
    }


    //利用双重循环
    public class Solution {
        public int largestRectangleArea(int[] height) {
            if(height==null)
                return 0;
            int i,j,S=0;
            for(i=0;i<height.length;i++){
                int minheight=Integer.MAX_VALUE;
                for(j=i;j<height.length;j++){
                    minheight=Math.min(minheight,height[j]);
                    S=Math.max(S,(j-i+1)*minheight);
                }
            }
            return S;
        }
    }


    public class Solution2 {
        public int largestRectangleArea(int[] height) {
            Stack<Integer> stack=new Stack<Integer>();
            if(height==null)
                return 0;
            int res=0;
            for(int i=0;i<height.length;i++){
                int count=0;
                if(stack.empty()){
                    stack.push(height[i]);
                    continue;
                }
                if(!stack.empty()&&height[i]>=stack.peek()){
                    stack.push(height[i]);
                }
                else{
                    while(!stack.empty()&&height[i]<stack.peek()){
                        count++;
                        res=Math.max(res,count*stack.pop());
                    }
                    for(int j=0;j<count;j++){
                        stack.push(height[i]);
                    }
                    stack.push(height[i]);
                }
            }
            for(int i=0;i<height.length;i++){
                res=Math.max(res,stack.pop()*(i+1));
            }
            return res;
        }
    }

    public class Solution3{
        class StackItem{
            public int height;
            public int index;

            public StackItem(int height, int index) {
                this.height = height;
                this.index = index;
            }
        }
        int MaxRectangleArea(int[] A,int n){
            int maxArea=0;
            if (A==null||A.length==0){
                return maxArea;
            }
            Stack<StackItem> stack=new Stack<StackItem>();
            //栈的最底部
            stack.push(new StackItem(Integer.MIN_VALUE,-1));
            for (int i = 0; i <=n; i++) {
                StackItem cur=new StackItem((i<n?A[i]:Integer.MIN_VALUE),i);
                if (cur.height>stack.peek().height){
                    stack.push(cur);
                    continue;
                }
                while (stack.size()>1){
                    StackItem prev=stack.peek();
                    int area=(i- prev.index)* prev.height;
                    maxArea=Math.max(area,maxArea);
                    prev.height= cur.height;
                    if (prev.height>stack.get(stack.size()-2).height){
                        break;
                    }
                    //只有if不成立的情况才会进行出栈
                    //分别是栈（size-2）等于和大于prev的值
                    stack.pop();
                }
            }
            return maxArea;
        }

    }
}
